package problem;

import instance.InstanceResultado;
import instance.InstanceTP3;

import java.util.Iterator;
import java.util.LinkedList;

public class BusquedaLocal {
		
	/* Funciones y sus aridades: */
	/*
	 * public BusquedaLocal (InstanceResultado inst, InstanceTP3 inst_pesos)
	 * 			Resuelve el problema. Al finalizar imprime la informacion sobre que decision final tomo.
	 * 			Modifica los circuitos pasados como parametro. 
	 * 
	 * private void modificarCircuitos(MejorParcial mp)
	 * 			Modifica los circuitos para dejar la solucion final.
	 * 
	 * private int calcularPesoTotal() 
	 * 			Devuelve el peso total con los datos usados en el constructor.
	 * 
	 * private int calcularOtroPesoTotal(InstanceResultado inst_circ)
	 * 			Devuelve el peso total con los circuitos pasados en inst_circ y los pesos usados en el constructor.
	 * 			Modifica los circuitos pasados como parametro.
	 * 
	 * private int calcularCostoDeAgregarIEntreW1yW2(int i, int v1, int v2)
	 * 			Calcula el costo de agregar al nodo i entre los nodos v1 y v2.	
	 * 
	 */
	
	private LinkedList<Integer> circuito1;
	private LinkedList<Integer> circuito2;
	private int[][] pesos;
	private int cant_nodos;
	private int nodo_origen;
	private InstanceTP3 pes;
	private int res;
	
	public static int contador_Local;
	public LinkedList<Integer> progreso_soluciones;
	public int cant_Iters;
	
//	public BusquedaLocal (LinkedList<Integer> c1, LinkedList<Integer> c2, int[][] pesos, int cant_nodos, int nodo_origen){
	public BusquedaLocal (InstanceResultado inst, InstanceTP3 inst_pesos){
		
		/*IMPORTANTE: dado que el rendimiento (tiempo) no es importante y para ahorrar código y tiempo de los 
		 * programadores, nos guardamos el progreso de las soluciones hasta llegar al mínimo local. */
		progreso_soluciones = new LinkedList<Integer>();
		cant_Iters=0;
		
		this.pesos = inst_pesos.matriz;
		this.pes = inst_pesos;
				/* La cantidad de nodos es la cantidad que esta en los ciclos mas el nodo_origen*/
		this.cant_nodos = inst.getPrimer_ciclo().size() + inst.getSegundo_ciclo().size() + 1;
		this.nodo_origen = inst.getNodo_origen();
		
				/* Agrego el nodo_origen al principio y al final de cada ciclo */
		this.circuito1 = inst.getPrimer_ciclo();
		this.circuito1.addFirst(this.nodo_origen);
		this.circuito1.addLast(this.nodo_origen);
		
		this.circuito2 = inst.getSegundo_ciclo();
		this.circuito2.addFirst(this.nodo_origen);
		this.circuito2.addLast(this.nodo_origen);
		
				/* En la iteracion i, en mp voy a tener la mejor solucion hasta ese momento */
		MejorParcial mp = new MejorParcial(calcularPesoTotal());
			/* Primero saco los nodos del primer ciclo */
		boolean minimo_local = false;
		while(!minimo_local){
				//		System.out.println("----------------------");
	//		System.out.println("\n"+mp+"\n");
	//		System.out.println("----------------------");
			MejorParcial mejorVecino = dameElMejorVecino();
			
			progreso_soluciones.add(mejorVecino.getPesoTotal());
			cant_Iters++;
			
//			System.out.println(mejorVecino.getPesoTotal());
			
			if(mp.getPesoTotal() > mejorVecino.getPesoTotal()){
				// pude mejorar lo que tenia
				mp = mejorVecino;
				modificarCircuitos(mejorVecino);
			}else{
				// si no pude mejorarlo
				minimo_local = true;
				// me voy
			}			
		}
		this.circuito1.removeFirst();
		this.circuito1.removeLast();
		this.circuito2.removeFirst();
		this.circuito2.removeLast();
		
		this.res = mp.getPesoTotal();
	}
	
	private MejorParcial dameElMejorVecino(){
		MejorParcial mp = new MejorParcial();
		int tmp, w1, w2, valor, pos1, pos2;
		Iterator<Integer> it, it2;
		
		if(this.circuito1.size() != 4){
			for(int i=1; i<this.circuito1.size()-1; i++){
				valor = this.circuito1.get(i);
					/* Saco el elemento i */
				this.circuito1.remove(i);
					
					/* Itero por el primer ciclo viendo el costo de agregar en cada par de nodos consecutivo */
				it = this.circuito1.iterator();
				pos1 = 0;
				it2 = this.circuito1.iterator();
				it2.next();
				pos2 = 1;
				while(it2.hasNext()){
					w1 = it.next().intValue();
					w2 = it2.next().intValue();
						/* Si este movimiento me mejora lo que tenia, actualizo. */
					if((tmp=calcularCostoDeAgregarIEntreW1yW2(valor, w1, w2)) < mp.getPesoTotal() || mp.getPesoTotal() == 0){
						mp.setI(valor); 			mp.setPesoTotal(tmp); 	mp.setW1(w1); 		mp.setW2(w2);
						mp.setPos1(pos1); 			mp.setPos2(pos2); 		mp.setIndex(i);
						mp.setCircuitoPoner(1);		mp.setCircuitoSacar(1);
					}
	
					pos1++;
					pos2++;
				}
				
					/* Ahora itero por el segundo ciclo */
				it = this.circuito2.iterator();
				pos1 = 0;
				it2 = this.circuito2.iterator();
				it2.next();
				pos2 = 1;
				while(it2.hasNext()){
					w1 = it.next().intValue();
					w2 = it2.next().intValue();
						/* Si este movimiento me mejora lo que tenia, actualizo. */
					if((tmp=calcularCostoDeAgregarIEntreW1yW2(valor, w1, w2)) < mp.getPesoTotal() || mp.getPesoTotal() == 0){
						mp.setI(valor); 			mp.setPesoTotal(tmp); 	mp.setW1(w1); 		mp.setW2(w2);
						mp.setPos1(pos1); 			mp.setPos2(pos2); 		mp.setIndex(i);
						mp.setCircuitoPoner(2);		mp.setCircuitoSacar(1);
					}
	
					pos1++;
					pos2++;
				}
				
					/* Vuelvo a agregar el elemento donde estaba */
				this.circuito1.add(i, valor);
			}
		}
			/* En este caso, voy a sacar los elementos del segundo circuito */
		if(this.circuito2.size() != 4){
			for(int i=1; i<this.circuito2.size()-1; i++){
				valor = this.circuito2.get(i);
				this.circuito2.remove(i);
				
					/* Itero por el primer ciclo viendo el costo de agregar en cada par de nodos consecutivo */
				it = this.circuito1.iterator();
				pos1 = 0;
				it2 = this.circuito1.iterator();
				it2.next();
				pos2 = 1;
				while(it2.hasNext()){
					w1 = it.next().intValue();
					w2 = it2.next().intValue();
						/* Si este movimiento me mejora lo que tenia, actualizo. */
					if((tmp=calcularCostoDeAgregarIEntreW1yW2(valor, w1, w2)) < mp.getPesoTotal() || mp.getPesoTotal() == 0){
						mp.setI(valor); 			mp.setPesoTotal(tmp); 	mp.setW1(w1); 		mp.setW2(w2);
						mp.setPos1(pos1); 			mp.setPos2(pos2); 		mp.setIndex(i);
						mp.setCircuitoPoner(1);		mp.setCircuitoSacar(2);
					}
		
					pos1++;
					pos2++;
				}
				
					/* Ahora itero por el segundo */
				it = this.circuito2.iterator();
				pos1 = 0;
				it2 = this.circuito2.iterator();
				pos2 = 1;
				it2.next();
				while(it2.hasNext()){
					w1 = it.next().intValue();
					w2 = it2.next().intValue();
					if((tmp=calcularCostoDeAgregarIEntreW1yW2(valor, w1, w2)) < mp.getPesoTotal() || mp.getPesoTotal() == 0){
						mp.setI(valor); 			mp.setPesoTotal(tmp); 	mp.setW1(w1); 		mp.setW2(w2); 
						mp.setPos1(pos1); 			mp.setPos2(pos2); 		mp.setIndex(i);
						mp.setCircuitoPoner(2);		mp.setCircuitoSacar(2);
					}
					pos1++;
					pos2++;
				}
				this.circuito2.add(i, valor);
			}
		}
		
		return mp;
	}

	private void modificarCircuitos(MejorParcial mp) {
		
		if(mp.getCircuitoSacar()==1){
			this.circuito1.remove(mp.getIndex());
		}else{
			this.circuito2.remove(mp.getIndex());
		}
		
		if(mp.getCircuitoPoner()==1){
			this.circuito1.add(mp.getPos2(), new Integer(mp.getI()));
		}else{
			this.circuito2.add(mp.getPos2(), new Integer(mp.getI()));
		}
		
	}

	private int calcularPesoTotal() {
		int peso = 0;
		int w1, w2;
		
		Iterator<Integer> it, it2;
		
		it = this.circuito1.iterator();
		it2 = this.circuito1.iterator();
		it2.next();
		while(it2.hasNext()){
			w1 = it.next().intValue();
			w2 = it2.next().intValue();
			
//			peso += this.pesos[w1][w2];
			peso += this.pes.getPos(w1, w2);
		}
		
		it = this.circuito2.iterator();
		it2 = this.circuito2.iterator();
		it2.next();
		while(it2.hasNext()){
			w1 = it.next().intValue();
//			if(!it.hasNext()) break;
			w2 = it2.next().intValue();
			
//			peso += this.pesos[w1][w2];
			peso += this.pes.getPos(w1, w2);
		}
		return peso;
	}
	
	public int calcularOtroPesoTotal(InstanceResultado inst_circ) {	
				/* Funci�n para calcular el peso de otro "posible" resultado */
				/* Se asume que los pesos son iguales que los usados en el constructor */
		int peso = 0;
		int w1, w2;
		
		LinkedList<Integer> c1 = inst_circ.getPrimer_ciclo();
		c1.addFirst(inst_circ.getNodo_origen());
		c1.addLast(inst_circ.getNodo_origen());
		
		LinkedList<Integer> c2 = inst_circ.getSegundo_ciclo();
		c2.addFirst(inst_circ.getNodo_origen());
		c2.addLast(inst_circ.getNodo_origen());
		Iterator<Integer> it, it2;
		
		it = c1.iterator();
		it2 = c1.iterator();
		it2.next();
		while(it2.hasNext()){
			w1 = it.next().intValue();
//			if(!it.hasNext()) break;
			w2 = it2.next().intValue();
			
//			peso += this.pesos[w1][w2];
			peso += this.pes.getPos(w1, w2);
		}
		
		it = c2.iterator();
		it2 = c2.iterator();
		it2.next();
		while(it2.hasNext()){
			w1 = it.next().intValue();
//			if(!it.hasNext()) break;
			w2 = it2.next().intValue();
			
//			peso += this.pesos[w1][w2];
			peso += this.pes.getPos(w1, w2);
			}
		
		return peso;
	}

	private int calcularCostoDeAgregarIEntreW1yW2(int i, int v1, int v2) {	//tested
		int peso = 0;
		int w1, w2;
		
		Iterator<Integer> it, it2;
		
		it = this.circuito1.iterator();
		it2 = this.circuito1.iterator();
		it2.next();
		while(it2.hasNext()){
			w1 = it.next().intValue();
			w2 = it2.next().intValue();
			if(w1==v1 && w2==v2){
				peso += this.pesos[w1][i] + this.pesos[i][w2];
			}else{
				if(w1==v2 && w2==v1){
					peso += this.pesos[w1][i] + this.pesos[i][w2];
				}
				else{
					peso += this.pesos[w1][w2];
				}
			}
			
		}
		
		it = this.circuito2.iterator();
		it2 = this.circuito2.iterator();
		it2.next();contador_Local+=5;
		contador_Local+=1;
		while(it2.hasNext()){
			w1 = it.next().intValue();
			w2 = it2.next().intValue();
			contador_Local+=6;
			contador_Local+=3;
			if(w1==v1 && w2==v2){
				peso += this.pesos[w1][i] + this.pesos[i][w2];
				contador_Local+=3;
			}
			else{
				contador_Local+=3;
				if(w1==v2 && w2==v1){
					peso += this.pesos[w1][i] + this.pesos[i][w2];
					contador_Local+=3;
				}
				else{
					peso += this.pesos[w1][w2];
					contador_Local+=2;
				}
			}
		}
		contador_Local+=1;
		return peso;
	}
	
	public int getRes(){
		return this.res;
	}

	public static void main(String[] args){
		int[][] matriz = new int[6][6];
		
		for(int i=0; i<6; i++){
				matriz[i][i] = 0;
		}
		
		matriz[0][1] = matriz[1][0] = 5;
		matriz[0][2] = matriz[2][0] = 1;
		matriz[0][3] = matriz[3][0] = 2;
		matriz[0][4] = matriz[4][0] = 3;
		matriz[0][5] = matriz[5][0] = 2;
		matriz[1][2] = matriz[2][1] = 3;
		matriz[1][3] = matriz[3][1] = 1;
		matriz[1][4] = matriz[4][1] = 3;
		matriz[1][5] = matriz[5][1] = 2;
		matriz[2][3] = matriz[3][2] = 4;
		matriz[2][4] = matriz[4][2] = 3;
		matriz[2][5] = matriz[5][2] = 2;
		matriz[3][4] = matriz[4][3] = 2;
		matriz[3][5] = matriz[5][3] = 3;
		matriz[4][5] = matriz[5][4] = 1;
			
		LinkedList<Integer> l1 = new LinkedList<Integer>();
//		l1.add(0);
		l1.add(1);
		l1.add(2);
		l1.add(3);
//		l1.add(0);
		
		Iterator<Integer> it = l1.iterator();
		it.next();
		Integer a = it.next();
		it.remove();	
		
		
//		System.out.println(l1);
		
//		System.out.println();
		l1.add(1, a);
		
		
		LinkedList<Integer> l2 = new LinkedList<Integer>();
//		l2.add(0);
		l2.add(4);
		l2.add(5);
//		l2.add(0);
		
//		System.out.println(l1);
//		System.out.println(l2);
		
		InstanceTP3 inst_pesos = new InstanceTP3(6, 0);
		inst_pesos.matriz = matriz;
		
		InstanceResultado inst_ciclos = new InstanceResultado();
		inst_ciclos.setPrimer_ciclo(l1);
		inst_ciclos.setSegundo_ciclo(l2);
		inst_ciclos.setNodo_origen(0);
		
//		BusquedaLocal bl = new BusquedaLocal(l1, l2, matriz, 5, 0);
		BusquedaLocal bl = new BusquedaLocal(inst_ciclos, inst_pesos);
		
		System.out.println(l1 + "\n" + l2);
		
		LinkedList<Integer> list_1 = new LinkedList<Integer>();
		list_1.add(1);
		list_1.add(2);
		list_1.add(3);
		
		LinkedList<Integer> list_2 = new LinkedList<Integer>();
		list_2.add(4);
		list_2.add(5);
		
		InstanceResultado ir2 = new InstanceResultado();
		ir2.setPrimer_ciclo(list_1);
		ir2.setSegundo_ciclo(list_2);
		ir2.setNodo_origen(0);
		
		
		System.out.println(bl.calcularOtroPesoTotal(ir2));
	
		System.out.println(list_1 + "\n" + list_2);
		
//		l1.remove(2); //saco el elemento que esta en la posicion 2 (que casualmente es el elemento 2)
//		System.out.println(bl.calcularCostoDeAgregarIEntreW1yW2(2, 4, 5));
		
	}
	
}
